package leetcode;

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {

	public static void main(String[] args) {
		String s = "bdab";
		String t = "ab";
		MinimumWindowSubstring object = new MinimumWindowSubstring();
		System.out.println(object.minWindow(s, t));
	}
	
	public String minWindow(String s, String t) {
		if(t.length() > s.length()){
			return "";
		}
		char[] sChas = s.toCharArray();
		char[] tChas = t.toCharArray();
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < tChas.length; i++) {
			map.put(tChas[i], map.getOrDefault(tChas[i], 0) + 1);
		}
		int count = tChas.length;	//获取到所有的字符个数
		
		//设置双指针
		int left = 0, right = 0;
		int start = 0;	//记录是从哪个下标开始的
		int matchLength = Integer.MAX_VALUE;	//匹配的最大长度
		while(right < sChas.length){
			if(map.containsKey(sChas[right])){
				map.put(sChas[right], map.get(sChas[right]) - 1);
			}else{
				map.put(sChas[right], -1);
			}
			if(map.get(sChas[right]) >= 0){
				count--;
			}
			//当找到与tChas的匹配时，count会变为0
			if(count == 0){
				//此时来进行移动
				//小于0说明这个字符是多的，可以去掉该字符
				while(map.get(sChas[left]) < 0){
					map.put(sChas[left], map.get(sChas[left++]) + 1);
				}
				System.out.println("left: " + left + "right: " + right);
				if(right - left + 1 < matchLength){
					matchLength = right - left + 1;
					start = left;
				}
				count++;
				map.put(sChas[left], map.get(sChas[left++]) + 1); 
			}
			right++;
		}
		if(matchLength == Integer.MAX_VALUE) return "";
		return s.substring(start, start + matchLength);
	}
}
